import java.util.Arrays;

/**
 * 二分查找
 */
public class BinarySearchBasic {
    /**
     * 二分查找  条件 有序数组！
     * 思路：
     * 左右两个指针，分别指向数组的首尾， 先取数组的中间，和目标数做比较，
     * 循环条件是左指针在右指针的左边或相对（可以想结束条件，左指针跑了右指针右边，说明找了一圈没找到）
     * 如果目标大于中间数，说明目标在中间数的右侧，就让左指针指向中间数的下一个位置
     * 如果目标小于中间数，说明目标在中间数的左侧，就让右指针指向中间数的上一个位置
     * 如果相等，说明找到了，返回下标即可
     * 如果左指针已经跑了右指针的右边说明，已经找了一圈了，没找到，结束返回-1
     * 问题一：  为什么循环条件是 i<=j  而不是i<j呢？ 如果i<j，会出现一中情况，要找的数在首尾，右指针一直变小，直到和左指针重叠，i=j应该刚好到了要找的数的位置，
     * 但是由于循环条件是i<j所以不会再走循环内的逻辑，也就找不出要找的数。因为之前我们比较的都是i,j和mid之间的比较，不能少了i和j也要进行比较
     * 问题二：  i+j / 2 会有问题？  如果 i 和 j 足够大， i+j 超过了int正整数能表示的范围，就会出现 +后变成了负数
     * 为什么会出现这种问题，因为计算机里的数是通过二进制存储的，在java中会把最高位看作是符号位，
     * 0100 0000 0000 0000 0000 0000 0000 0000    1073741824
     * 0111 1111 1111 1111 1111 1111 1111 1110    2147483646
     * 1011 1111 1111 1111 1111 1111 1111 1110    3221225470   同样一个 二进制 的数，如果不考虑符号位
     * 1011 1111 1111 1111 1111 1111 1111 1110   -1073741826   同样一个 二进制 的数，如果最高位看到符号位，就表示负数。
     * 如何解决 超过了int表示范围，导致二进制 最高位作为符号位 出现的负数问题，  >>> 就要用到 无符号右移的操作符， 看一看作除2向下取整 为什么可以这么看 因为二进制数 1001 (9)  右移一位  0100 (4)
     * 1011 1111 1111 1111 1111 1111 1111 1110 >>>   -1073741826   不管是不是负数，右移运算，最高位都会变成0
     * 0101 1111 1111 1111 1111 1111 1111 1111  这个数又在int的表示范围内，  右移运算不仅在java实用，在js也适用，记住他是二进制的位运算，
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] a = {1, 3, 5, 6, 7, 8, 9};//[1,3,5,6,7,8,9]
        System.out.println(binarySearchBasic(a, 5));

        useJavaArrayBinarySearch();
    }


    public static int binarySearchBasic(int[] a, int target) {
        int i = 0;              //左指针 , 指向a数组的第一个元素
        int j = a.length - 1;   //右指针 ，指向a数组的最后一个元素
        while (i <= j) {              //  -----易错点 容易漏掉i=j的情况
            int mid = (i + j) >>> 1;  //中间值    ----易错点
            if (target < a[mid]) {  //目标在中间值的右边
                j = mid - 1;
            } else if (a[mid] < target) { //目标在中间值左边
                i = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }


    /**
     * 改动前，两个指针
     * 12  9  8  0  17  6
     * ⬆               ⬆
     * 改动版， 是将数据右边界作为j的值， 而不是数据a的最大索引值,不是查找的目标
     * 12  9  8  0  17  6
     * ⬆                  ⬆
     */
    public static int binarySearchAlternative(int[] a, int target) {
        int i = 0;          //左指针，指向a数组的第一个元素
        int j = a.length;   //右指针，将数组的的右边外边界 作为右指针  相当于[) 左闭右开
        while (i < j) {     //这里不能有=， 可能发生死循环， 当要查找当元素么有在数组中 就可能发生死循环
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;    //右指针 永远指向边界外
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 上面的算法 如果要找的元素在最左边，那么循环里面 每次的比较只会执行一次  但如果要找的元素在最右边那么循环里每次的比较都会执行两次，
     * 假设循环执行了L次， 如果元素在最左边 那么比较进行了L次， 如果元素在最右边，那么比较进行了2L次  相当于多比较了一倍的次数
     * 为了减少比较的次数，下面采用平衡的方式
     * <p>
     * <p>
     * <p>
     * 平衡法的思路 不是在循环内去找元素 循环是为了缩小边界，什么时候待查范围只剩下一个元素，在退出循环去比较是否是目标
     * 12  9  8  0  17  6      i最初指向最左元素，j指向边界，所以 每次循环的j都不是待查找元素 [) 左闭右开
     * ⬆  ⬆                  此时j-i=1 当待查找元素只剩下一个的时候就退出循环
     * <p>
     * 平衡法 减少循环内的比较次数
     */
    public static int binarySearchBalance(int[] a, int target) {
        int i = 0;
        int j = a.length;
        while (1 < j - i) {      //j-i 代表 数组内 待查找的元素个数
            int m = (i + j) >>> 1;
            if (target < a[m]) {    //if-else 循环内只会比较一次
                j = m;
            } else {
                i = m;    //此处 中间值也是待查找的元素 所以 做边界不能m+1
            }
        }
        //当j-i <=1 就退出上面的循环，此时a[i]就是最后一个待查找的元素，跟目标值比较
        if (a[i] == target) {
            return i;
        } else {
            return -1;
        }
    }

    /**
     * java 中的二分查找 使用
     */
    public static void useJavaArrayBinarySearch() {
        int[] a = {1, 3, 5, 6, 7, 8, 9};
        System.out.println(Arrays.binarySearch(a, 5)); // 返回值是2， 表示 要查找的元素在数组内，且下标是2
        System.out.println(Arrays.binarySearch(a, 2));  // 返回值是是-2， 表示 要查找的元素不在数组内，如果要插入该元素，要插入的下标位置是(-2+1 取正数) 也就是1 ，即插入2这个元素，下表应该是1
    }                                                       // 为什么java的二分查找返回值是   return -(low + 1);， 这是为了区分0, 因为+0 和-0 无法区分，所以返回个0不知道到底是 存在且下表为0  还是不存在要插入的位置是0


    /**
     * java 中的数组元素copy      向数组中copy新元素的数组copy
     */
    public void copyArrayItem() {
        int[] a = {1, 3, 5, 6, 7, 8, 9};
        int i = Arrays.binarySearch(a, 2);
        if (i < 0) {
            int InsertIndex = Math.abs(i + 1);  //元素2要插入的下标位置
            int[] b = new int[a.length + 1];
            System.arraycopy(a, 0, b, 0, InsertIndex);  //将a数组的元素 拷贝到b， 从0开始到InsertIndex结束 [) 左闭右开
            b[InsertIndex] = 2; //加入2 到对应位置
            System.arraycopy(a, InsertIndex, b, InsertIndex + 1, a.length - InsertIndex); //再将剩余的a的元素copy到b中
        }
    }


    /**
     * 找  最靠左元素坐标   找不到返回-1
     */
    public static int binarySearchBasicLeftMost1(int[] a, int target) {
        int i = 0;              //左指针 , 指向a数组的第一个元素
        int j = a.length - 1;   //右指针 ，指向a数组的最后一个元素
        int candidate = -1; //候选者
        while (i <= j) {              //  -----易错点 容易漏掉i=j的情况
            int mid = (i + j) >>> 1;  //中间值    ----易错点
            if (target < a[mid]) {  //目标在中间值的右边
                j = mid - 1;
            } else if (a[mid] < target) { //目标在中间值左边
                i = mid + 1;
            } else {
                //记录找到的位置 ,如果找到了新的 就覆盖掉
                candidate = mid;
                //缩小边界
                j = mid - 1;
            }
        }
        return candidate;
    }

    /**
     * 找  最靠右元素坐标   找不到返回-1
     */
    public static int binarySearchBasicRightMost1(int[] a, int target) {
        int i = 0;              //左指针 , 指向a数组的第一个元素
        int j = a.length - 1;   //右指针 ，指向a数组的最后一个元素
        int candidate = -1; //候选者
        while (i <= j) {              //  -----易错点 容易漏掉i=j的情况
            int mid = (i + j) >>> 1;  //中间值    ----易错点
            if (target < a[mid]) {  //目标在中间值的右边
                j = mid - 1;
            } else if (a[mid] < target) { //目标在中间值左边
                i = mid + 1;
            } else {
                //记录找到的位置 ,如果找到了新的 就覆盖掉
                candidate = mid;
                //缩小边界
                i = mid + 1;
            }
        }
        return candidate;
    }

    /**
     * 二分查找   返回 >=目标  的 最靠左 索引位置
     *
     * @param a
     * @param target
     * @return
     */

    public static int binarySearchBasicLeftMost3(int[] a, int target) {
        int i = 0;              //左指针 , 指向a数组的第一个元素
        int j = a.length - 1;   //右指针 ，指向a数组的最后一个元素
        while (i <= j) {              //  -----易错点 容易漏掉i=j的情况
            int mid = (i + j) >>> 1;  //中间值    ----易错点
            if (target <= a[mid]) {  //目标在中间值的右边
                j = mid - 1;
            } else { //目标在中间值左边
                i = mid + 1;
            }
        }
        return i;
    }


    /**
     * 二分查找   返回 <=目标  的 最靠右 索引位置
     *
     * @param a
     * @param target
     * @return
     */
    public static int binarySearchBasicLeftMost4(int[] a, int target) {
        int i = 0;              //左指针 , 指向a数组的第一个元素
        int j = a.length - 1;   //右指针 ，指向a数组的最后一个元素
        while (i <= j) {              //  -----易错点 容易漏掉i=j的情况
            int mid = (i + j) >>> 1;  //中间值    ----易错点
            if (target < a[mid]) {  //目标在中间值的右边
                j = mid - 1;
            } else { //目标在中间值左边
                i = mid + 1;
            }
        }
        return i - 1;
    }

    /**
     * 二分查找的三种写法
     */
    //写法1
    public int binarySearchVer1(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;  //左右指针 分别指向 数组的 最左和 最右 元素
        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (target < a[mid]) {
                j = mid - 1;
            } else if (a[mid] < target) {
                i = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    //写法2
    public int binarySearchVer2(int[] a, int target) {
        int i = 0;
        int j = a.length;   //右指针指向 数组的末尾的下一个下标
        while (i < j) {
            int mid = (i + j) >>> 1;
            if (target < a[mid]) {
                j = mid;
            } else if (a[mid] < target) {
                i = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    //写法3
    public int binarySearchVer3(int[] a, int target) {
        int i = 0;
        int j = a.length;
        while (i < j - 1) {
            int mid = (i + j) >>> 1;
            if (target < a[mid]) {
                j = mid;
            } else {
                i = mid;
            }
        }
        return (a[i] == target) ? i : -1;
    }

    /**
     * 力扣  704. 二分查找
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
     */
    public int search704(int[] nums, int target) {
        int i = 0;
        int j = nums.length;   //右指针指向 数组的末尾的下一个下标
        while (i < j) {
            int mid = (i + j) >>> 1;
            if (target < nums[mid]) {
                j = mid;
            } else if (nums[mid] < target) {
                i = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 力扣 35. 搜索插入位置
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * 请必须使用时间复杂度为 O(log n) 的算法。
     * 输入: nums = [1,3,5,6], target = 2
     * 输出: 1
     */
    //这里用 二分查找的 leftmost 变种解决
    public int searchInsert(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (target < nums[mid]) {
                j = mid - 1;
            } else if (nums[mid] < target) {
                i = mid + 1;
            } else {  //如果相等，就继续往前找，因为可能存在相同重复的元素， 一直找到最左边的元素位置
                j = mid - 1;
            }
        }
        return i;
    }

    //优化上面的 if 分支
    public int searchInsert1(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (target <= nums[mid]) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return i;
    }

    /**
     * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
     */
    public int[] searchRange(int[] nums, int target) {
        int leftMost = leftMost(nums, target);
        if( leftMost == -1 ){
            return  new int[]{-1,-1};
        }else{
            return  new int[]{leftMost, rightMost(nums, target)};
        }
    }

    public int leftMost(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        int candidate = -1;
        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (target < nums[mid]) {
                j = mid - 1;
            } else if (nums[mid] < target) {
                i = mid + 1;
            } else {
                candidate = mid;
                j = mid - 1;
            }
        }
        return candidate;
    }

    public int rightMost(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        int candidate = -1;
        while (i <= j) {
            int mid = (i + j) >>> 1;
            if (target < nums[mid]) {
                j = mid - 1;
            } else if (nums[mid] < target) {
                i = mid + 1;
            } else {
                candidate = mid;
                i = mid + 1;
            }
        }
        return candidate;
    }
}

